﻿#region Copyright 2012 by Roger Knapp, Licensed under the Apache License, Version 2.0
/* Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#endregion
using System;
using System.Collections.Generic;

namespace CSharpTest.Net.Data
{
    /// <summary>
    /// A Guid struct for creating sequentially advancing unique identifiers
    /// </summary>
    /// <remarks>
    /// Bits  - usage
    /// 00-03 - Reserved, always 000 if generated with DbGuid.NewGuid()
    /// 03-52 - Represent bits 3-52 of the DateTime.UtcNow.Ticks value
    /// 52-80 - 25 bits of incrementing numeric value
    /// 64-66 - Guid type constant of 111, or 001 if IsSqlGuid is true
    /// 76-128- Randomly generated bytes
    /// </remarks>
    public struct DbGuid : IFormattable, IComparable, IEquatable<DbGuid>, IComparable<DbGuid>
    {
        /// <summary> Returns an empty DbGuid structure. </summary>
        public static readonly DbGuid Empty;
        
        const long SqlTypeMask = unchecked((0x20L << 56));
        const long BinTypeMask = unchecked((0xE0L << 56));
        const int BufferSize = 1024 * 6;

        // _nextSequence is an AppDomain specific unique value who's 25 least significant bits are merged
        // to ensure each guid in this domain is guarunteed to be unique given the assumption that not
        // more than 2^25th (33,554,432) DBGuids are generated per millisecond.
        static int _nextSequence;

        #region RandomByte()

        static readonly System.Security.Cryptography.RandomNumberGenerator _rnGenerator;
        static readonly byte[] _randomBytes;
        static int _nextRandomByte;

        static DbGuid()
        {
            Empty = new DbGuid();
            _rnGenerator = new System.Security.Cryptography.RNGCryptoServiceProvider();
            _randomBytes = new byte[BufferSize];
            _nextRandomByte = BufferSize;
            _nextSequence = Guid.NewGuid().GetHashCode() & 0x00FFFFFF;
        }

        static byte RandomByte()
        {
            while(true)
            {
                int offset = System.Threading.Interlocked.Increment(ref _nextRandomByte);
                if (offset < BufferSize)
                    return _randomBytes[offset];

                lock (_randomBytes)
                {
                    if (_nextRandomByte >= BufferSize)
                    {
                        _rnGenerator.GetBytes(_randomBytes);
                        System.Threading.Interlocked.Exchange(ref _nextRandomByte, 0);
                        return _randomBytes[0];
                    }
                }
            }
        }
        
        #endregion

        /// <summary>
        /// Creates a (mostly) sequential DbGuid using 7 bytes of DateTime in UTC ticks, 
        /// 3 bytes of a sequentially incremented random value, and 6 bytes of random data.
        /// </summary>
        /// <remarks>
        /// I say this is *mostly* sequential, because sometime after 2^24 (16m) guids are generated, the 25-bit 
        /// incrementing number will 'roll over'.  When this occurs and multiple guids are generated within the
        /// 4ms time window during this event, then it is possible that some may be out of sequence until the 4ms
        /// window passes.  This anomaly in the sequencing should have no practical impact on performance.
        /// 
        /// The collision chance within AppDomain are essentially non-existent due to the use of the incremented
        /// value.  Across domains or processes the collision chance requires that Guids are generated within a
        /// 4ms window, happen to have the same 25-bit incremented value, and generate the same random 6-byte 
        /// sequence while using cryptographic-strength PRNG.
        /// 
        /// It's important to know that sequential guids like this drastically reduce the entropy size of the
        /// random value.  Therefore DbGuid is more likely to produce duplicates than a regular fully-randomized
        /// guid.  If you want to do the math on the collision probability of the 73-bit random value see the
        /// wikipedia article on the birthday paradox:  http://en.wikipedia.org/wiki/Birthday_problem
        /// Keep in mind you must factor in the 4ms time interval with which DbGuids are timestamped. I'm not
        /// a math genius or anything, but generating a duplicate DbGuid is going to be more probable than 
        /// generating a duplicate random guid, and less probable than being eaten by a shark.
        /// </remarks>
        public static DbGuid NewGuid()
        {
            return new DbGuid(true);
        }

        private readonly long _h64;
        private readonly long _l64;

        private DbGuid(bool initialize)
        {
            unchecked
            {
                long sequenceNum = System.Threading.Interlocked.Increment(ref _nextSequence);
                _h64 = (DateTime.UtcNow.Ticks & ~(BinTypeMask | 0x0FFF)) | ((sequenceNum >> 13) & 0x0FFFL);
                _l64 = (sequenceNum << 48) | BinTypeMask
                    | (long)RandomByte() << 40
                    | (long)RandomByte() << 32
                    | (long)RandomByte() << 24
                    | (long)RandomByte() << 16
                    | (long)RandomByte() << 8
                    | RandomByte();
            }
        }

        /// <summary>
        /// Constructs a DbGuid from two 64-bit values
        /// </summary>
        public DbGuid(long a, long b)
        {
            _h64 = a;
            _l64 = b;
        }

        /// <summary>
        /// Constructs a DbGuid from the typical Guid values
        /// </summary>
        public DbGuid(int a, short b, short c, byte d, byte e, byte f, byte g, byte h, byte i, byte j, byte k)
        {
            unchecked
            {
                _h64 = ((long)a) << 32 | ((long)(uint)b) << 16 | ((long)(uint)c);
                _l64 = ((long) d) << 56
                       | ((long) e) << 48
                       | ((long) f) << 40
                       | ((long) g) << 32
                       | ((long) h) << 24
                       | ((long) i) << 16
                       | ((long) j) << 8
                       | ((long) k) << 0;
            }
        }

        /// <summary> Creates a DbGuid from a System.Guid instance. </summary>
        /// <remarks> 
        /// Unexpected results may occur if using System.Guid.NewGuid() to initialize this instance. 
        /// Instead use DbGuid.NewGuid() to construct a new identifier.  This is provided primarily
        /// for conversion and use with other systems (i.e. SqlServer, etc).
        /// </remarks>
        public DbGuid(Guid guid) : this(true, guid.ToByteArray(), 0) { }

        /// <summary>
        /// Constructs a DbGuid from an array of 16 (or more) bytes.
        /// </summary>
        public DbGuid(byte[] bytes) : this(false, bytes, 0) { }
        
        /// <summary>
        /// Constructs a DbGuid from an array of 16 (or more) bytes beginning at the offset supplied.
        /// </summary>
        public DbGuid(byte[] bytes, int offset) : this(false, bytes, offset)
        { }

        /// <summary>
        /// Constructs a DbGuid from an array of 16 (or more) bytes beginning at the offset supplied.
        /// System.Guid.ToByteArray is little-endian, DbGuid.ToByteArray is in big-endian format.
        /// </summary>
        public DbGuid(bool littleEndian, byte[] bytes, int offset)
        {
            if (bytes == null)
                throw new ArgumentNullException("bytes");
            if ((bytes.Length - offset) < 16)
                throw new ArgumentOutOfRangeException("bytes");
            if (littleEndian)
            {
                byte tmp = bytes[offset];
                bytes[offset] = bytes[offset + 3];
                bytes[offset + 3] = tmp;

                tmp = bytes[offset + 1];
                bytes[offset + 1] = bytes[offset + 2];
                bytes[offset + 2] = tmp;

                tmp = bytes[offset + 4];
                bytes[offset + 4] = bytes[offset + 5];
                bytes[offset + 5] = tmp;

                tmp = bytes[offset + 6];
                bytes[offset + 6] = bytes[offset + 7];
                bytes[offset + 7] = tmp;
            }
            unchecked
            {
                _h64 = (long)bytes[offset++] << 56
                    | (long)bytes[offset++] << 48
                    | (long)bytes[offset++] << 40
                    | (long)bytes[offset++] << 32
                    | (long)bytes[offset++] << 24
                    | (long)bytes[offset++] << 16
                    | (long)bytes[offset++] << 8
                    | (long)bytes[offset++] << 0;
                _l64 = (long)bytes[offset++] << 56
                    | (long)bytes[offset++] << 48
                    | (long)bytes[offset++] << 40
                    | (long)bytes[offset++] << 32
                    | (long)bytes[offset++] << 24
                    | (long)bytes[offset++] << 16
                    | (long)bytes[offset++] << 8
                    | (long)bytes[offset] << 0;
            }
        }

        /// <summary> Returns the first/high 64 bits as a long </summary>
        public long High64 { get { return _h64; } }
        /// <summary> Returns the second/low 64 bits as a long </summary>
        public long Low64 { get { return _l64; } }

            /// <summary>
        /// Returns the value as a System.Guid type.
        /// </summary>
        public Guid ToGuid()
        {
            return new Guid(
                (int)(_h64 >> 32),
                (short)(_h64 >> 16),
                (short)(_h64 >> 0),
                (byte)(_l64 >> 56),
                (byte)(_l64 >> 48),
                (byte)(_l64 >> 40),
                (byte)(_l64 >> 32),
                (byte)(_l64 >> 24),
                (byte)(_l64 >> 16),
                (byte)(_l64 >> 8),
                (byte)(_l64 >> 0)
            );
        }
        
        /// <summary>
        /// Returns the UTC DateTime the guid was created.  Will not work with ToSqlGuid().
        /// </summary>
        public DateTime ToDateTimeUtc()
        {
            return IsSqlGuid 
                ? new DateTime(_l64 & ~BinTypeMask, DateTimeKind.Utc)
                : new DateTime(_h64, DateTimeKind.Utc);
        }

        /// <summary>
        /// Used to swap the first 8 bytes with the last 8 bytes for SQL-Server optimization.
        /// The inverse operation can be performed by calling ToSequenceGuid() on the result.
        /// If IsSqlGuid is already True this call has no effect and returns the same value.
        /// </summary>
        public DbGuid ToSqlGuid()
        {
            return IsSqlGuid ? this : new DbGuid(_l64 & ~BinTypeMask, (_h64 & ~BinTypeMask) | SqlTypeMask);
        }

        /// <summary>
        /// Used to reverse the effects of ToSqlGuid() and obtain a guid who's ToByteArray result
        /// is sequential.
        /// If IsSqlGuid is already False this call has no effect and returns the same value.
        /// </summary>
        public DbGuid ToSequenceGuid()
        {
            return !IsSqlGuid ? this : new DbGuid(_l64 & ~BinTypeMask, (_h64 & ~BinTypeMask) | BinTypeMask);
        }

        /// <summary>
        /// Returns true if the DbGuid is the result of a call to ToSqlGuid.
        /// </summary>
        public bool IsSqlGuid { get { return (_l64 & BinTypeMask) == SqlTypeMask; } }

        /// <summary>
        /// Big-endian byte array, not compatible with System.Guid.ToByteArray.
        /// </summary>
        public byte[] ToByteArray()
        {
            byte[] bytes = new byte[16];
            ToByteArray(bytes, 0);
            return bytes;
        }
        
        /// <summary>
        /// Copies the big-endian byte array to the offset supplied, not compatible
        /// with System.Guid.ToByteArray.
        /// </summary>
        public void ToByteArray(byte[] bytes, int offset)
        {
            if (bytes == null) 
                throw new ArgumentNullException();
            if (bytes.Length - offset < 16)
                throw new ArgumentOutOfRangeException("offset");
            unchecked
            {
                bytes[offset++] = (byte)(_h64 >> 56);
                bytes[offset++] = (byte)(_h64 >> 48);
                bytes[offset++] = (byte)(_h64 >> 40);
                bytes[offset++] = (byte)(_h64 >> 32);
                bytes[offset++] = (byte)(_h64 >> 24);
                bytes[offset++] = (byte)(_h64 >> 16);
                bytes[offset++] = (byte)(_h64 >> 8);
                bytes[offset++] = (byte)(_h64 >> 0);

                bytes[offset++] = (byte)(_l64 >> 56);
                bytes[offset++] = (byte)(_l64 >> 48);
                bytes[offset++] = (byte)(_l64 >> 40);
                bytes[offset++] = (byte)(_l64 >> 32);
                bytes[offset++] = (byte)(_l64 >> 24);
                bytes[offset++] = (byte)(_l64 >> 16);
                bytes[offset++] = (byte)(_l64 >> 8);
                bytes[offset] = (byte)(_l64 >> 0);
            }
        }

        #region Object overloads

        /// <summary>
        /// Returns the fully qualified type name of this instance.
        /// </summary>
        public override string ToString()
        {
            return ToSequenceGuid().ToGuid().ToString();
        }

        /// <summary>
        /// Returns the fully qualified type name of this instance.
        /// </summary>
        public string ToString(string format)
        {
            return ToSequenceGuid().ToGuid().ToString(format);
        }

        /// <summary>
        /// Indicates whether this instance and a specified object are equal.
        /// </summary>
        public override bool Equals(object obj)
        {
            if (!(obj is DbGuid)) return false;
            return Equals((DbGuid)obj);
        }

        /// <summary>
        /// Returns the hash code for this instance.
        /// </summary>
        public override int GetHashCode()
        {
            long result = (_h64 ^ _l64) | BinTypeMask;
            return unchecked((int)(result ^ (result >> 32)));
        }

        #endregion

        #region IEquatable<DbGuid> Members

        /// <summary>
        /// Indicates whether the current object is equal to another object of the same type.
        /// </summary>
        public bool Equals(DbGuid other)
        {
            return CompareTo(other) == 0;
        }

        #endregion

        #region IComparable Members

        int IComparable.CompareTo(object obj)
        {
            if (obj is DbGuid)
                return CompareTo((DbGuid)obj);
            return 1;
        }

        #endregion

        #region IComparable<DbGuid> Members

        /// <summary>
        /// Compares the current object with another object of the same type.
        /// </summary>
        public int CompareTo(DbGuid other)
        {
            long ha, hb, la, lb;

            if (IsSqlGuid)
            {
                ha = _l64 & ~BinTypeMask;
                la = _h64 & ~BinTypeMask;
            }
            else
            {
                ha = _h64 & ~BinTypeMask;
                la = _l64 & ~BinTypeMask;
            }
            if (other.IsSqlGuid)
            {
                hb = other._l64 & ~BinTypeMask;
                lb = other._h64 & ~BinTypeMask;
            }
            else
            {
                hb = other._h64 & ~BinTypeMask;
                lb = other._l64 & ~BinTypeMask;
            }

            if (ha == hb)
            {
                if (la == lb)
                    return 0;
                if (la < lb)
                    return -1;
            }
            else if (ha < hb)
                return -1;
            return 1;
        }

        #endregion

        #region IFormattable Members

        /// <summary>
        /// Formats the value of the current instance using the specified format.
        /// </summary>
        public string ToString(string format, IFormatProvider formatProvider)
        {
            return ToSequenceGuid().ToGuid().ToString(format, formatProvider);
        }

        #endregion

        #region Equality Operators
        /// <summary> Compares the two objects for non-reference equality </summary>
        public static bool operator ==(DbGuid x, DbGuid y)
        {
            return x.Equals(y);
        }
        /// <summary> Compares the two objects for non-reference equality </summary>
        public static bool operator !=(DbGuid x, DbGuid y)
        {
            return !x.Equals(y);
        }
        #endregion

        #region Comparison Operators
        /// <summary> Compares the two objects </summary>
        public static bool operator >(DbGuid x, DbGuid y)
        {
            return x.CompareTo(y) > 0;
        }
        /// <summary> Compares the two objects </summary>
        public static bool operator >=(DbGuid x, DbGuid y)
        {
            return x.CompareTo(y) >= 0;
        }
        /// <summary> Compares the two objects </summary>
        public static bool operator <(DbGuid x, DbGuid y)
        {
            return x.CompareTo(y) < 0;
        }
        /// <summary> Compares the two objects </summary>
        public static bool operator <=(DbGuid x, DbGuid y)
        {
            return x.CompareTo(y) <= 0;
        }
        #endregion

        #region Implicit Guid Cast

        /// <summary> Converts the DbGuid to a System.Guid </summary>
        public static implicit operator Guid(DbGuid value) { return value.ToGuid(); }
        /// <summary> Converts a System.Guid to a DbGuid </summary>
        public static explicit operator DbGuid(Guid value) { return new DbGuid(value); }

        #endregion

        /// <summary>
        /// Implementation of a comparer and equality comparer for DbGuid
        /// </summary>
        public sealed class DbGuidComparer : IComparer<DbGuid>, IEqualityComparer<DbGuid>
        {
            /// <summary>
            /// Compares two objects and returns a value indicating whether one is less than, equal to, or greater than the other.
            /// </summary>
            public int Compare(DbGuid x, DbGuid y)
            {
                return x.CompareTo(y);
            }
            /// <summary>
            /// Determines whether the specified objects are equal.
            /// </summary>
            public bool Equals(DbGuid x, DbGuid y)
            {
                return x.Equals(y);
            }
            /// <summary>
            /// Returns a hash code for the specified object.
            /// </summary>
            public int GetHashCode(DbGuid obj)
            {
                return obj.GetHashCode();
            }
        }

        /// <summary>
        /// Returns a comparer for comparing equality or sorting DbGuid instances
        /// </summary>
        public static readonly DbGuidComparer Comparer = new DbGuidComparer();

        class DbGuidSerializer : CSharpTest.Net.Serialization.ISerializer<DbGuid>
        {
            void CSharpTest.Net.Serialization.ISerializer<DbGuid>.WriteTo(DbGuid value, System.IO.Stream stream)
            {
                unchecked
                {
                    CSharpTest.Net.Serialization.PrimitiveSerializer.UInt64.WriteTo((ulong)value._h64, stream);
                    CSharpTest.Net.Serialization.PrimitiveSerializer.UInt64.WriteTo((ulong)value._l64, stream);
                }
            }
            DbGuid CSharpTest.Net.Serialization.ISerializer<DbGuid>.ReadFrom(System.IO.Stream stream)
            {
                unchecked
                {
                    return new DbGuid(
                        (long)CSharpTest.Net.Serialization.PrimitiveSerializer.UInt64.ReadFrom(stream),
                        (long)CSharpTest.Net.Serialization.PrimitiveSerializer.UInt64.ReadFrom(stream)
                    );
                }
            }
        }

        /// <summary>
        /// Returns a serializer that can read/write a DbGuid to and from a stream.
        /// </summary>
        public static readonly CSharpTest.Net.Serialization.ISerializer<DbGuid> Serializer = new DbGuidSerializer();
    }
}
